#ifndef TACORES_DIJKSTRA_H
#define TACORES_DIJKSTRA_H

using namespace std;

#include "Graph.h"
#include <vector>
#include <queue>
#include <limits>

// O((V+E)*log V)
class Dijkstra
{
public:
	Dijkstra(Graph& g)
		: g (g)
	{
	}

	void singleSourceShortest(int s)
	{
		initialize();
		dist[s] = 0;

		priority_queue<P, vector<P>, greater<P> > pq;
		int size = g.numVertices();
		for(int i = 0; i < size; ++i)
		{
			pq.push(P(dist[i], i));
		}

		while(pq.empty() == false)
		{
			P p = pq.top(); pq.pop();
			int d = p.first;
			int u = p.second;
			if(dist[u] < d)
			{
				continue;
			}

			VertexList::const_iterator end = g.end(u);
			for(VertexList::const_iterator it = g.begin(u); it != end; it++)
			{
				int v = it->first;
				int newLen = dist[u] + g.edgeWeight(u, v);
				if(newLen < dist[v])
				{
					dist[v] = newLen;
					pred[v] = u;
					pq.push(P(newLen, v));
				}
			}
		}
	}
	vector<int> getPredecessor() { return pred; }
	vector<int> getDistance() { return dist; }

private:
	void initialize()
	{
		int size = g.numVertices();
		dist.assign(size, numeric_limits<int>::max());
		pred.assign(size, -1);
	}

	Graph& g;
	vector<int> dist;
	vector<int> pred;

	typedef pair<int,int> P;
};
typedef Dijkstra DQSTR;

#endif

